package com.zwj.interview.排序;

import java.util.Random;

/**
 * 题目：请从一个乱序数组中找出第k大的数字。例如，数组[3，1，2，4，5，5，6]中第3大的数字是5
 */
public class 求数组中第k大的元素 {

    /**
     * 分析：
     * 在长度为n的排序数组中，第k大的数字的下标是n-k。下面用快速排序的函数partition对数组分区，
     * 如果函数partition选取的中间值在分区之后的下标正好是n-k，分区后左边的值都比中间值小，
     * 右边的值都比中间值大，即使整个数组不是排序的，中间值也肯定是第k大的数字
     * <p>
     * 如果函数partition选取的中间值在分区之后的下标大于n-k，那么第k大的数字一定位于中间值的左侧，
     * 于是再对中间值左侧的子数组分区。类似地，如果函数partition选取的中间值在分区之后的下标小于n-k，
     * 那么第k大的数字一定位于中间值的右侧，于是再对中间值右侧的子数组分区。
     * 重复这个过程，直到函数partition的返回值正好是下标为n-k的位置
     */
    public int findKThLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0;
        int end = nums.length - 1;
        int index = partition(nums, start, end);
        while (index != target) {
            if (index > target) {
                end = index - 1;
            } else {
                start = index + 1;
            }
            //推进指针之后，再进行分区计算
            index = partition(nums, start, end);
        }
        return nums[index];

    }


    private int partition(int[] nums, int start, int end) {
        //随机选取的值
        int random = new Random().nextInt(end - start + 1) + start;
        //将选取的值和数组末尾的数字进行交换
        swap(nums, random, end);
        //交换过后，数组最后一位就是之前选取的中间值
        int p1 = start - 1;
        for (int p2 = start; p2 < end; ++p2) {
            if (nums[p2] < nums[end]) {
                p1++;
                //交换位置i和末尾的数字
                swap(nums, p2, p1);
            }
        }
        //走到这说明一轮扫描已经结束，此时的p2指针已经到达数组最后，那么推进p1，然后交换指针P1和P2指向的数字
        p1++;
        swap(nums, p1, end);
        return p1;
    }


    /**
     * 交换数组中两个下标的值
     *
     * @param nums
     * @param index1
     * @param index2
     */
    private void swap(int[] nums, int index1, int index2) {
        if (index1 != index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }




}
